package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         141,
		Discription: "判断链表是否成环",
		Level:       1,
		Labels: map[string]int{
			"链表":   1,
			"快慢指针": 1,
		},
	})
}

func HasCycle(head *ds.ListNode) bool {
	if head == nil {
		return false
	}

	fast := head.Next
	slow := head
	for fast != slow {
		//注意fast是移动两次的，所以要判断下一位和下两位
		//如果没有环，fast肯定先于slow变为nil，所以只需判空fast即可
		if fast == nil || fast.Next == nil {
			return false
		}

		fast = fast.Next.Next
		slow = slow.Next
	}

	return true
}
